package com.xigua._数学;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 0,1,···,n-1这n个数字排成一个圆圈，
 * 从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
 *例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
 *
 * @date 2022/3/2521:22
 */
public class _剑指Offer62_圆圈中最后剩下的数字 {

    public static void main(String[] args) {
        lastRemaining(10,5);
    }

    public static int lastRemaining(int n, int m) {
        if (n==1)return 0;
        int x =lastRemaining(n-1,m);
        return (m+x)%n;
    }

    /// 数学+迭代 (约瑟夫环)
    // 对于[n, m问题]，首轮删除环中第m个数字后，得到一个长度为 n - 1 的数字环。由于有可能 m > n，因此删除的数字为 (m - 1) % n，删除后的数字环从下个数字(即m % n)开始，
// 设 t = m % n，可得"新数字环"在"旧数字环"中的对应下标为: 【 t，t+1，t+2，...，0，1，...，t-3，t- 2 】（t-1为被删除的数字）
//
// 删除一轮后的数字环变为[n-1，m问题]，其数字下标对应关系如下:
//	      新环下标(本环)    新环下标在旧环(上环)下标中对应的下标
//			   0                      (t+0)%n                      (旧环删除数字nums[(m-1)%n]后的新环的起始下标为 旧环中的m%n(t))
//			   1                      (t+1)%n
//			  ...                      ...
//			  n-2                     (t+n-2)%n
//
// 所以新环中的下标x 与在旧环中对应下标X 的关系为 X = (t + x) % n   (这里的x为新环中所有的下标，但最终新环只有一个元素，下标为0！)
// 删除到最后的新环中只有一个元素，下标为0，可以通过下标递推关系 找出其在"最旧环"中的下标!
//
//  X = (t + x) % n   --->  f(X) = (t + f(X - 1)) % n         (f(X - 1)为旧环下标，f(X)为旧环在其"上一层"新环中对应的下标)
//                    --->       = (m % n + f(X - 1)) % n
//                    --->       = (m + f(X - 1)) % n         (m % n % n == m % n)
    public static int lastRemaining1(int n, int m) {
        int x = 0;                        // 最新一环，只有一个元素，下标为0 ("该元素"即最后剩下的数字)
        for (int i = 2; i <= n; ++i) {    // 开始推导"该元素"在旧环、旧旧环、...中的下标，其直接旧环有两个元素，所以i=2，一直推到i=n(即最初环)
            x = (m + x) % i;              // 迭代，先推出"该元素"在直接旧环中的下标，在利用该下标继续上推！
        }
        return x;                    // 最终推出"该元素"在最初环中对应的下标，这里下标对应的值==下标值，直接返回！
    }

}
